P3195 [HNOI2008]玩具装箱TOY

这道题像我这样的 dpdp 蒟蒻都能一眼看出 dpdp 式:

sumsumcc 的前缀和,则有

dp[i]=min{dp[j]+((ij1)+(sum[i]sum[j])L)2}  (0j<i)dp[i]=min\{ dp[j]+((i-j-1)+(sum[i]-sum[j])-L)^2 \} ~~ (0 \le j < i)

就可以Θ(n2)\Theta(n^2)解决了 ,开O2骗了70分

考虑优化,令si=sum[i]+is_i=sum[i]+i,则有:

dp[i]=min{dp[j]+(sisj1L)2}    (0j<i)dp[i]=min\{ dp[j] + (s_i-s_j-1-L)^2 \} ~~~~ (0 \le j < i)

si1Ls_i-1-L 看作一个整体拆开平方(它们与决策点 jj 无关),得到:

dp[i]=min{dp[j]+sj22×sj×(siL1)}+(siL1)2    (0j<0)dp[i]=min\{ dp[j] + {s_j}^2 - 2 \times s_j \times (s_i-L-1) \}+(s_i-L-1)^2 ~~~~ (0 \le j < 0)

dp[i]=min{dp[j]+sj22sisj+2Lsj+2sj}+(siL1)2    (0j<0)dp[i]=min\{ dp[j] + {s_j}^2 - 2s_is_j + 2Ls_j + 2s_j \}+(s_i-L-1)^2 ~~~~ (0 \le j < 0)

然后是斜优的套路,设两个决策点 j,k(j<k)j,k (j<k)jj 优于 kk。即:

dp[j]+sj22sisj+2Lsj+2sj<dp[k]+sk22sisk+2Lsk+2skdp[j] + {s_j}^2 - 2s_is_j + 2Ls_j + 2s_j<dp[k] + {s_k}^2 - 2s_is_k + 2Ls_k + 2s_k

(dp[j]+sj2)(dp[k]+sk2)+2L(sjsk)+2(sjsk)<2si(sjsk)(dp[j]+{s_j}^2)-(dp[k]+{s_k}^2)+2L(s_j-s_k)+2(s_j-s_k)<2s_i(s_j-s_k)

注意sj<sks_j<s_k , 移项变号:

(dp[j]+sj2)(dp[k]+sk2)+2(L+1)(sjsk)sjsk>2si\frac{(dp[j]+{s_j}^2)-(dp[k]+{s_k}^2)+2(L+1)(s_j-s_k)}{s_j-s_k}>2s_i

(dp[j]+sj2+2sj(L+1))(dp[k]+sk2+2sk(L+1))sjsk>2si\frac{(dp[j]+{s_j}^2+2s_j(L+1))-(dp[k]+{s_k}^2+2s_k(L+1))}{s_j-s_k}>2s_i

现在就可以维护一个下凸包解决,时间复杂度Θ(n)\Theta(n)

#include <cstdio>
#include <iostream>
using namespace std;
#define LL long long

const int MAXN = 50000;
int n , l , c[ MAXN + 5 ] , Head = 1 , Tail = 0 , Que[ MAXN + 5 ];
LL sum[ MAXN + 5 ] , dp[ MAXN + 5 ];

LL Calc( int i ) {
    return sum[ i ] + i;
}
double Slope( int u , int v ) {
    return ( ( dp[ u ] + Calc( u ) * Calc( u ) + 2 * Calc( u ) * ( l + 1 ) ) - ( dp[ v ] + Calc( v ) * Calc( v )+ 2 * Calc( v ) * ( l + 1 ) ) ) / ( Calc( u ) - Calc( v ) );
}

int main( ) {
    scanf("%d %d",&n,&l);
    for( int i = 1 ; i <= n ; i ++ )
        scanf("%d",&c[ i ]) , sum[ i ] = sum[ i - 1 ] + c[ i ];
    
    Que[ ++ Tail ] = 0;
    for( int i = 1 ; i <= n ; i ++ ) {
        while( Head < Tail && Slope( Que[ Head ] , Que[ Head + 1 ] ) < 2 * Calc( i ) ) Head ++;

        dp[ i ] = dp[ Que[ Head ] ] + ( Calc( i ) - Calc( Que[ Head ] ) - 1 - l ) * ( Calc( i ) - Calc( Que[ Head ] ) - 1 - l );
        while( Head < Tail && Slope( Que[ Tail - 1 ] , Que[ Tail ] ) > Slope( Que[ Tail - 1 ] , i ) ) Tail --;
        Que[ ++ Tail ] = i;
    }

    printf("%lld",dp[ n ]);
    return 0;
}